package cn.njupt.cmpSort;
//归并排序
public class MergeSort<E extends Comparable<E>> extends Sort<E> {
    //辅助数组，长度为原数组的一半
    private E[] help;

    @Override
    public void sort() {
        //本来写的是new Object[array.length>>1],这边是转为E,E是Comparable的子类，所以强转会有问题
        help= (E[]) new Comparable[array.length>>1];
        sort(0,array.length);
    }

    //排序[begin,end)
    public void sort(int begin,int end){
        if(end-begin<2){
            return;
        }
        int mid=(begin+end)>>1;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }
    //合并
    private void merge(int begin, int mid, int end) {
        //左边数组[begin,mid)  右边数组[mid,end)
        int l1=begin,e1=mid;
        int l2=mid,e2=end;
        //将左边数组复制到help数组中
        for (int i = begin; i <mid ; i++) {
            help[i-begin]=array[i];
        }
        //如果左边数组先结束复制，那么右边数组就不用再复制了，结束循环即可
        while(l1<e1){
//          但是如果右边数组先结束，我们就直接复制左边数组就可以了，即下面的else
            if(l2<e2 &&cmpElements(array[l1],array[l2])>0){
                array[begin++]=array[l2++];
            }else{
                array[begin++]=array[l1++];
            }
        }

    }
}
